/**
 * @BelongsProject : LeetCode
 * @Author : WXY
 * @CreateTime : 2022-12-07  10:01
 * @Description : 剑指 Offer 10- I. 斐波那契数列
 * @Version : 1.0
 */

public class Num10_fib {
    public static int fib1(int n) {
        if (n == 0) return 0;
        if (n == 1) return 1;
        return fib1(n - 1) + fib1(n - 2);
    }

    public static int fib(int n) {
        if (n == 0 || n == 2) return n;
        int[] dp = new int[n + 1];
        dp[0] = 0;
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            dp[i] = (dp[i - 1] + dp[i - 2]) % 1000000007;
        }
        return dp[n];
    }

    public static int fib2(int n) {
        if (n == 0 || n == 1)return n;
        int[] dp = new int[n + 1];
        dp[1] = 1;
        dp[2] = 1;
        process(n, dp);
        return dp[n];
    }

    private static int process(int n, int[] dp) {
        if (n == 1|| n == 0)return n;
        if (n == 2)return 1;
        if (dp[n] == 0)
            dp[n] = process(n - 1, dp) + process(n - 2, dp);
        dp[n] = dp[n] % 1000000007;
        return dp[n];
    }

    public static void main(String[] args) {
        int fib = fib(1);
        System.out.println(fib);
        System.out.println(fib2(2));
        System.out.println(fib1(10));
        System.out.println(fib(10));

    }
}
